package com.wangjie.binarysearch;

/**
 * @author jieshao
 * @date 2022/4/21 17:02
 *
 * 1011. 在 D 天内送达包裹的能力
 */
public class Test04 {
    public int shipWithinDays(int[] weights, int days) {
        // 船的最小载重是数组中元素的最大值，因为每次至少得装一件货物走，最大载重是数组中所有元素之和，也就是一次把所有货物都运走
        int left = 0;
        // [left, right) right 是开区间，所以额外加 1
        int right = 1;
        for (int w : weights) {
            left = Math.max(left, w);
            right += w;
        }
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (f(weights, mid) <= days) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    // 定义：x 为船的运载能力(重量/天)，f(x) 天运完所有货物，f(x) 随 x 的增加单调递减
    public int f(int[] weights, int x) {
        int days = 0;
        for (int i = 0; i < weights.length; ) {
            // 每天能运多少货
            int cap = x;
            while (i < weights.length) {
                // 货物重量超过运载量，放到第二天再运
                if (cap < weights[i]) {
                    break;
                }
                // 剩余运载量
                cap -= weights[i];
                i++;
            }
            days++;
        }
        return days;
    }
}